小白带你学 | 您所在的位置:网站首页 › greedy algorithms are › 小白带你学 |
贪心算法(Greedy Algorithm) 简介 贪心算法,又名贪婪法,是寻找最优解问题的常用方法,这种方法模式一般将求解过程分成若干个步骤,但每个步骤都应用贪心原则,选取当前状态下最好/最优的选择(局部最有利的选择),并以此希望最后堆叠出的结果也是最好/最优的解。{看着这个名字,贪心,贪婪这两字的内在含义最为关键。这就好像一个贪婪的人,他事事都想要眼前看到最好的那个,看不到长远的东西,也不为最终的结果和将来着想,贪图眼前局部的利益最大化,有点走一步看一步的感觉。} 贪婪法的基本步骤: 步骤1:从某个初始解出发;步骤2:采用迭代的过程,当可以向目标前进一步时,就根据局部最优策略,得到一部分解,缩小问题规模;步骤3:将所有解综合起来。 事例一:找零钱问题 假设你开了间小店,不能电子支付,钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币,如果你是售货员且要找给客户 41 分钱的硬币,如何安排才能找给客人的钱既正确且硬币的个数又最少? 这里需要明确的几个点:1.货币只有 25 分、10 分、5 分和 1 分四种硬币;2.找给客户 41 分钱的硬币;3.硬币最少化 思考,能使用我们今天学到的贪婪算法吗?怎么做? (回顾一下上文贪婪法的基本步骤,1,2,3) 1.找给顾客sum_money=41分钱,可选择的是25 分、10 分、5 分和 1 分四种硬币。能找25分的,不找10分的原则,初次先找给顾客25分;2.还差顾客sum_money=41-25=16。然后从25 分、10 分、5 分和 1 分四种硬币选取局部最优的给顾客,也就是选10分的,此时sum_money=16-10=6。重复迭代过程,还需要sum_money=6-5=1,sum_money=1-1=0。至此,顾客收到零钱,交易结束;3.此时41分,分成了1个25,1个10,1个5,1个1,共四枚硬币。 编程实现 #include using namespace std; #define ONEFEN 1 #define FIVEFEN 5 #define TENFEN 10 #define TWENTYFINEFEN 25 int main() { int sum_money=41; int num_25=0,num_10=0,num_5=0,num_1=0; //不断尝试每一种硬币 while(money>=TWENTYFINEFEN) { num_25++; sum_money -=TWENTYFINEFEN; } while(money>=TENFEN) { num_10++; sum_money -=TENFEN; } while(money>=FIVEFEN) { num_5++; sum_money -=FIVEFEN; } while(money>=ONEFEN) { num_1++; sum_money -=ONEFEN; } //输出结果 cout |
CopyRight 2018-2019 实验室设备网 版权所有 |